4道黑题

小帅出生在1100年 666

题目（信奥团队里的） 这个代码主要是娱乐向owo 温馨提示：结果自动对998244353取模，数据太大用可能会对减法和除法影响 宣传图片 注意：要输入负数-X要打括号，而且要输入0-X，否则会爆栈！！！

汇总 前序遍历: 中序遍历: 后序遍历: 给个点赞吧,球球了

#深度优先搜索 1.vis 标记 ->回溯 2.剪枝 1.可行性 2.连通性 ##连通性问题

#include<bits/stdc++.h> using namespace std; int a[5],n,k; int vis[100]; void dfs(int x){ if(x==n){ for(int i=1;i<=n;i++){ cout<<a[i]<<' '; } cout<<endl; return; } for(int i=1;i<=k;i++){ if(!vis[i]){ vis[i]=1; a[x+1]=i; dfs(x+1); vis[i]=0; } } int main(){ cin>>k>>n; dfs(0); }

AKSZ-深度优先搜索 排列组合（ A (N,M) )($ *****) ) A (n,m) =n(n-1)(n-2)......(n-m+1) *****)=A(n,m)/A(m,m)=n(n-1)(n-2)......(n-m+1)/m! 排列代码 组合代码 DFS 1.标记（vis[]->回溯（vis[i]=0）） 2.剪枝 > 1.可行性 > 2.最优性 > 3.连通性

深度优先搜索 在解空间里找到一个最好的解 排列组合 A(N,M) = N*(N-1)...(N-M+1) *****) = A(N,M) / A(M,M) 寻找组合用保证数组单调递增的方法 回溯 用来防止重复运行同种操作 先用vis数组标记，然后回到之前的状态 一般的题方法：dfs+剪枝（+回溯） 连通性问题 不用回溯 直接标记

深度优先搜索 1.回溯：洛谷P1219 2.剪枝（可行性，最优性）：洛谷P1135,P2392,P3624 3.连通性问题：acgoA8003 搜索：解空间 排列：A(n,m)=n*(n-1)......(n-m+1) 组合：*****)=A(n,m)/A(m,m)=[nn(n-1)......(n-m+1)]/m(m-1)......*1 回溯

深度优先搜索 排列、组合 A(n,m) = 在n个元素中选择m个进行排列 A(n,m)=n∗(n−1)∗...∗(n−m+1)A(n,m) = n * (n-1) * ... * (n-m+1) A(n,m)=n∗(n−1)∗...∗(n−m+1) *****) = 在n个元素中选择m个进行组合(无重复) *****)=A(n,m)/A(m,m)=[n∗(n−1)∗...∗(n−m+1)]/m!*****) = A(n,m)/A(m,m) = [ n * (n-1) * ...* (n-m+1) ] / m! *****)=A(n,m)/A(m,m)=[n∗(n−1)∗...∗(n−m+1)]/m! 组合排序(定序)： 剪枝 过程中去掉超过范围的状态 可行性https://www.luogu.com.cn/problem/B3624 最优性https://www.acgo.cn/problemset/8051/info 连通性

#include <iostream> using namespace std; long long comb(int n, int m) { if (m == 0 || m == n) { return 1; } long long dp[n + 1][n + 1]; for (int i = 0; i <= n; i++) { dp[i][0] = 1; dp[i][i] = 1; } for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) { dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % 1000000007; } } return dp[n][m]; } int main() { int n, m; cin >> n >> m; cout << comb(n, m) << endl; return 0; }

#include <iostream> using namespace std; int fibonacci(int n) { if (n == 1 || n == 2) { return 1; } return fibonacci(n - 1) + fibonacci(n - 2); } int main() { int n; cin >> n; cout << fibonacci(n) << endl; return 0; }

#include <iostream> using namespace std; int main() { int n; cin >> n; int dp[51]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; ++i) { dp[i] = dp[i-1] + dp[i-2]; } cout << dp[n] << endl; return 0; }

#include<bits/stdc++.h> using namespace std; long long x[51]; int n; int main(){ cin>>n; x[1]=1; x[2]=2; for(int i=3;i<=n;i++){ x[i]=x[i-1]+x[i-2]; } cout<<x[n]; return 0; }

#include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int a[n];a[0]=1;a[1]=1; for(int i=2;i<n;i++){ a[i]=a[i-1]+a[i-2]; } cout<<a[n-1]; }

官方快增加团队公告栏的字数啊！！! 我团队的公告栏已经满了！ 顺便招个人

题目描述 楼梯有 n 个台阶，上楼可以一步上一阶，也可以一步上两阶。一共有多少种上楼的方法？ 输入格式 输入一个整数 n（0 < n ≤ 50）n（0<n≤50）。 输出格式 输出上到第 nn 级台阶一共有多少种方法。 输入输出样例 输入#1 复制 4 输出#1 复制 5 说明/提示 样例一解释： 上到 4级台阶总共有 5 种方案。